package algorithms.leecode;

import java.util.ArrayList;
import java.util.List;

public class Au51 {
    public static List<List<String>> solveNQueens(int n) {
        // 原矩阵
        List<List<String>> resultList = new ArrayList<>();
        int len = n;
        boolean[] protoX = new boolean[n]; // 纵列
        boolean[] protoY = new boolean[n]; // 横列
        // 原矩阵旋转45度的
        int n45 = 2 * n - 1;
        boolean[] newX = new boolean[n45];
        boolean[] newY = new boolean[n45];
        char[][] arrs = new char[n][n];
        // 初始化矩阵
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                arrs[i][j] = '.';
            }
        }
        fps(n, arrs, protoX, protoY, newX, newY, 0,resultList);
        return resultList;
    }

    public static void fps(int n,char[][] arrs
            ,boolean[] protoX
            ,boolean[] protoY
            ,boolean[] newX
            ,boolean[] newY
            ,int indexY
    , List<List<String>> resultList) {
        if (indexY == n) {
            List<String> list = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                char[] arr = arrs[i];
                String a = new String(arr);
                list.add(a);
            }
            resultList.add(list);
        }


        for (int i = 0; i < n; i++) {
            if (protoX[i]) {
                continue;
            }
            if (protoY[indexY]) {
                continue;
            }
            // 旋转矩阵的横纵坐标
            int nx = n - 1 - indexY + i;
            int ny = indexY + i;
            if (newX[nx]) {
                continue;
            }
            if (newY[ny]) {
                continue;
            }
            arrs[i][indexY] = 'Q';
            protoX[i] = true;
            protoY[indexY] = true;
            newX[nx] = true;
            newY[ny] = true;
            // 回朔
            fps(n, arrs, protoX, protoY, newX, newY, indexY + 1,resultList);
            arrs[i][indexY] = '.';
            protoX[i] = false;
            protoY[indexY] = false;
            newX[nx] = false;
            newY[ny] = false;

        }

    }

    public static void main(String[] args) {
        solveNQueens(1);
    }
}
